/*
2021-7-11
RBVree by shio
introduce
A:每个节点不是黑色就是红色,根节点必为黑色
B:父子节点不能都为红
C:叶子节点都为黑色
D:任意一个节点到其叶子节点的所有路径中，经过的黑色节点数相同
*/

#ifndef _RBTREE_H
#define _RBTREE_H
#include<iostream>
namespace rbtree
{
    typedef bool __color_type;
    const __color_type __rb_tree_red=false;
    const __color_type __rb_tree_black=true;

    template<class K,class V>
    struct RBNode
    {
    public:
        RBNode():parent(nullptr),lchild(nullptr),rchild(nullptr),colors(__rb_tree_red)
        {}

    public:
        typedef RBNode<K,V>* __rb_ptr;
        typedef K key;
        typedef V value;
        __rb_ptr parent;
        __rb_ptr lchild;
        __rb_ptr rchild;
        key _key;
        value _value;
        __color_type colors;

    private:
        RBNode& operator=(const RBNode& temp);
    };

    template<class K,class V>
    class RBTree
    {
    public:
        RBTree():rb_root(nullptr),_size(0)
        {
            rb_head=new RBNode<K,V>();
            rb_head->lchild=rb_head;
            rb_head->rchild=rb_head;
        }
        RBTree(const RBTree<K,V>& temp);
        RBTree<K,V>& operator=(const RBTree<K,V>& temp);

    public:
        typedef K key;
        typedef V value;
        typedef RBNode<K,V>* __rb_ptr;
        typedef size_t num;
        __rb_ptr rb_root;
        __rb_ptr rb_head;
        num _size;
    public:
        bool Empty()
        {
            if(rb_root==nullptr)
                return true;
            return false;
        }
        
        __rb_ptr find_key(K _key)
        {

        }

        inline void __rb_tree_rotate_left(__rb_ptr x,__rb_ptr& root)
        {
            __rb_ptr y=x->parent->rchild;
            x->rchild=y->lchild;
            if(y->lchild!=nullptr)
                y->lchild->parent=x;
            if(x==root)
                root=x;
            else if(x==x->parent->lchild)
                x->parent->lchild=y;
            else
                x->parent->rchild=y;
            y->lchild=x;
            x->parent=y;
        }

        inline void __rb_tree_rotate_right(__rb_ptr x,__rb_ptr& root)
        {
            __rb_ptr y=x->parent->lchild;
            x->lchild=y->rchild;
            if(y->rchild!=nullptr)
                y->rchild->parent=x;
            else if(x==x->parent->lchild)
                x->parent->lchild=y;
            else
                x->parent->rchild=y;
            y->rchild=x;
            x->parent=y;
        }

        inline void __rb_tree_rebalance(__rb_ptr x,__rb_ptr& root)
        {
            while(x!=root&&x->parent->colors==__rb_tree_red)
            {
                if(x->parent==x->parent->parent->lchild)
                {
                    __rb_ptr y=x->parent->parent->rchild;
                    if(y&&y->colors==__rb_tree_red)
                    {
                        x->parent->colors=__rb_tree_black;
                        y->colors=__rb_tree_black;
                        x->parent->parent->colors=__rb_tree_red;
                        x=x->parent->parent;
                    }
                    else
                    {
                        if(x==x->parent->rchild)
                        {
                            x=x->parent;
                            __rb_tree_rotate_left(x,root);
                        }
                        x->parent->colors=__rb_tree_black;
                        x->parent->parent->colors=__rb_tree_red;
                        __rb_tree_rotate_right(x->parent->parent,root);
                    }
                }
                else
                {
                    __rb_ptr y=x->parent->parent->lchild;
                    if(y&&y->colors==__rb_tree_red)
                    {
                        x->parent->colors=__rb_tree_black;
                        y->colors=__rb_tree_black;
                        x->parent->parent->colors=__rb_tree_red;
                        x=x->parent->parent;
                    }
                    else
                    {
                        if(x==x->parent->lchild)
                        {
                            x=x->parent;
                            __rb_tree_rotate_left(x,root);
                        }
                        x->parent->colors=__rb_tree_black;
                        x->parent->parent->colors=__rb_tree_red;
                        __rb_tree_rotate_right(x->parent->parent,root);
                    }
                }
            }
            root->colors=__rb_tree_black;
        }

        int insert_unique(key _key,value _value)
        {
            __rb_ptr x=rb_root;
            __rb_ptr y=rb_head;
            while(x!=nullptr)
            {
                y=x;
                if(x->_key==_key)
                    return -1;
                x->_key>_key?x=x->lchild:x=x->rchild;
            }
            x=new RBNode<K,V>();
            x->parent=y;
            x->_key=_key;
            x->_value=_value;
            if(y->_key>_key)
                y->lchild=x;
            else
                y->rchild=x;
            if(rb_root==nullptr)
            {
                rb_root=x;
                rb_head->parent=x;
            }
            __rb_tree_rebalance(x,rb_root);
            _size++;
        }

        void __erase_node(__rb_ptr& x)
        {
            __rb_ptr y=nullptr;
            if(x==x->parent->lchild)
            {
                y=x->parent->rchild;
                if(y->colors==__rb_tree_red)//兄弟节点为红，必有两个黑色侄儿
                {
                    y->colors=__rb_tree_black;
                    x->parent->colors=__rb_tree_red;
                    __rb_tree_rotate_left(x->parent,rb_root);
                    __erase_node(x);
                }
                if(y->rchild&&y->rchild->colors==__rb_tree_red)//侄儿节点为红
                {
                    y->colors=x->parent->colors;
                    x->parent->colors=__rb_tree_black;
                    y->rchild->colors=__rb_tree_black;
                    __rb_tree_rotate_left(x->parent,rb_root);
                }
                if(y->lchild&&y->lchild->colors==__rb_tree_red)//侄儿节点为红
                {
                    y->colors=__rb_tree_red;
                    y->lchild->colors=__rb_tree_black;
                    __rb_tree_rotate_right(y,rb_root);
                    __erase_node(x);
                }
                if(x->parent->colors==__rb_tree_red)//父节点为红
                {
                    x->parent->colors=__rb_tree_black;
                    y->colors=__rb_tree_red;
                }
                else//父节点、兄弟节点都为黑色，且无红色侄儿
                {
                    y->colors=__rb_tree_red;
                    __erase_node(x->parent);
                }
            }
            else
            {
                y=x->parent->lchild;
                if(y->colors==__rb_tree_red)
                {
                    y->colors=__rb_tree_black;
                    x->parent->colors=__rb_tree_red;
                    __rb_tree_rotate_right(x->parent,rb_root);
                    __erase_node(x);
                }
                if(y->lchild&&y->lchild->colors==__rb_tree_red)
                {
                    y->colors=x->parent->colors;
                    x->parent->colors=__rb_tree_black;
                    y->lchild->colors=__rb_tree_black;
                    __rb_tree_rotate_right(x->parent,rb_root);
                }
                if(y->rchild&&y->rchild->colors==__rb_tree_red)
                {
                    y->colors=__rb_tree_red;
                    y->rchild->colors=__rb_tree_black;
                    __rb_tree_rotate_left(y,rb_root);
                    __erase_node(x);
                }
                if(x->parent->colors==__rb_tree_red)
                {
                    x->parent->colors=__rb_tree_black;
                    y->colors=__rb_tree_red;
                }
                else
                {
                    y->colors=__rb_tree_red;
                    __erase_node(x->parent);
                }
            }
        }

        int delete_node(__rb_ptr x)
        {
            
            if(x->lchild==nullptr&&x->rchild==nullptr)
            {
                if(x->colors==__rb_tree_red)
                {
                    if(x==x->parent->lchild)
                        x->parent->lchild=nullptr;
                    else
                        x->parent->rchild=nullptr;
                    delete x;
                    x=nullptr;
                }
                else
                {
                    if(rb_root==x)
                    {
                        delete x;
                        x=nullptr;
                        rb_root=nullptr;
                    }
                    else
                    {
                        __rb_ptr y=x;
                        __erase_node(x);
                        delete y;
                        y=nullptr;
                    }
                }
            }
            else if(x->lchild==nullptr||x->rchild==nullptr)
            {
                __rb_ptr y=nullptr;
                if(x->lchild==nullptr)
                {
                    y=x->rchild;
                    x->_key=y->_key;
                    x->_value=y->_value;
                    x->rchild=nullptr;
                }
                else
                {
                    y=x->lchild;
                    x->_key=y->_key;
                    x->_value=y->_value;
                    x->lchild=nullptr;
                }
                delete y;
                y=nullptr;
            }
            else
            {
                __rb_ptr y=x->lchild,temp=y;
                while(y!=nullptr)
                {
                    temp=y;
                    y=y->rchild;
                }
                x->_key=temp->_key;
                x->_value=temp->_value;
                delete_node(temp);
            }
            _size--;
        }
    };
}

#endif

/*
重要性质：--根据路径黑节点数相同原理
A：红色节点要么没有孩子，要么就一定有两个黑孩子
B：黑色节点一定有兄弟节点，可黑可红，但一定有

插入：
首先新插入的节点都是红色，所以当插入位置的父节点是黑色时，直接插入不需要调整，父节点为红时调整
主要有两种情况
A：不存在伯父节点或者为黑色，则将父节点涂黑，祖父节点涂红并左旋或右旋
    如果插入节点与父节点不在同一方向，则需要先旋转调整至同一方向后做上述步骤
B：存在伯父节点且为红色，将父节点与伯父节点涂黑，祖父节点涂红，然后将祖父节点作为插入点
    继续循环向上调整，直至平衡

删除：
两种颜色（黑红）、三种孩子（无孩子、一个孩子、两个孩子） 2×3=6种组合
A：叶子节点（无孩子），如果为红色直接删除
    为黑色需要结合父亲和兄弟节点综合处理
    如果兄弟节点为黑，且有红色孩子，先将孩子旋转到同一方向，再父节点向删除节点方向旋转变色
    如果兄弟节点为黑，没有有红色孩子，若父节点为红，则父节点涂黑，兄弟节点涂红
    如果兄弟节点为黑，没有有红色孩子，父节点为黑，则父节点黑色权值加一并向上继续调整，兄弟节点涂红
    如果兄弟节点为红，父节点必为黑，父节点涂红并左旋，兄弟节点涂黑
B：一个孩子：这种情况下，只有黑父红子一种情况，黑父黑子或者红父黑子这两种会导致一边黑节点多不平衡
    可画图验证，这种情况只需要将黑节点删除，红子补上并涂黑即可
C：两个孩子：找前驱和后继转换成A、B两种情况
*/